﻿// 0806train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;


/*
 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
 */

int solve01(int n)
{
    vector<int>dp_vec(n+1);
    dp_vec[0] = 0;
    dp_vec[1] = 1;

    for (int i=2; i<=n; i++)
    {
        dp_vec[i] = dp_vec[i - 1] + dp_vec[i - 2];

    }

    return dp_vec[n];
}

/*
 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示：
1 <= n <= 45
 */

int solve02(int n)
{
    //n==0 0
    //n==1 1
    //n==2 0+1
    vector<int>dp_vec(n+1);
    dp_vec[0] = 0;
    dp_vec[1] = 1;
    dp_vec[2] = 2;

    for (int i=3; i<=n; i++)
    {
        dp_vec[i] = dp_vec[i - 1] + dp_vec[i - 2];
    }
    return dp_vec[n];
}


/*
 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
 */

void InitDpVec(vector<vector<int>>&dynamic_vec,int row, int col)
{
    for (int r_1 = 0; r_1 < row; r_1++)
    {
        for (int c_2 = 0; c_2 < col; c_2++)
        {
            if (r_1 == 0)
            {
                dynamic_vec[0][c_2] = 1;
            }

            if (c_2 == 0)
            {
                dynamic_vec[r_1][0] = 1;
            }
        }
    }
}

int solve03(int m, int n)
{
    int row = m;
    int col = n;

    vector<vector<int>>dynamic_vec(row, vector<int>(col));

    InitDpVec(dynamic_vec, row, col);

    for (int r_1 = 1; r_1 < row; r_1++)
    {
        for (int c_2 = 1; c_2 < col; c_2++)
        {
            dynamic_vec[r_1][c_2] = dynamic_vec[r_1 - 1][c_2] + dynamic_vec[r_1][c_2 - 1];
        }
    }
    return dynamic_vec[row - 1][col - 1];
}


/*
 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。
 机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。
机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。

示例1
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
 */
void InitGrid04(vector<vector<int>>&dynamic_grid, vector<vector<int>>& obstacleGrid)
{
    int row_size = obstacleGrid.size();
    int col_size = obstacleGrid[0].size();
    for (int r_1=0; r_1<row_size; r_1++)
    {
        //说明有障碍
        if (obstacleGrid[r_1][0] == 1) break;

        //第0列，只有一条路径
        dynamic_grid[r_1][0] = 1;
    }

    for (int c_1=0; c_1<col_size; c_1++)
    {
        if (obstacleGrid[0][c_1] == 1)break;

        //第0行，只有一条路径
        dynamic_grid[0][c_1] = 1;
    }


    //------
}

int solve04(vector<vector<int>>& obstacleGrid)
{
    int row_size = obstacleGrid.size();
    int col_size = obstacleGrid[0].size();

    vector<vector<int>>dynamic_grid(row_size, vector<int>(col_size));

    InitGrid04(dynamic_grid, obstacleGrid);


    for (int r_1=1; r_1< row_size; r_1++)
    {
	    for (int c_1=1; c_1<col_size; c_1++)
	    {
            if (obstacleGrid[r_1][c_1] == 1) continue;
            dynamic_grid[r_1][c_1] = dynamic_grid[r_1 - 1][c_1] + dynamic_grid[r_1][c_1 - 1];
	    }
    }
    return dynamic_grid[row_size - 1][col_size - 1];
    //solve04
}


int main()
{
    //obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    vector<int>vec_1 = { 0,0,0 };
    vector<int>vec_2 = { 0,1,0 };
    vector<int>vec_3 = { 0,0,0 };

    vector<vector<int>>oh_vec = { vec_1,vec_2,vec_3 };

    cout << solve04(oh_vec);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
